﻿#include"tree.h"


// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
    if (*pi >= n) return NULL;
    BTNode* node = NULL;
    if (a[*pi] != '#') {
        node = (BTNode*)malloc(sizeof(BTNode));
        node->_data = a[(*pi)++];
        node->_left = BinaryTreeCreate(a, n, pi); // 递归左子树
        node->_right = BinaryTreeCreate(a, n, pi); // 递归右子树 
    }
    else {
        (*pi)++; // 跳过'#' 
    }
    return node;

}


// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
    if (*root == NULL) return;
    BinaryTreeDestory(&(*root)->_left); // 销毁左子树 
    BinaryTreeDestory(&(*root)->_right); // 销毁右子树 
    free(*root); // 释放当前节点
    *root = NULL; // 确保指针置空
}



// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{

    if (root == NULL) return 0;
    return 1 + BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right);

}



// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{

    if (root == NULL) return 0;
    if (root->_left == NULL && root->_right == NULL) return 1;
    return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}



// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
    if (root == NULL) return 0;
    if (k == 1) return 1;
    return BinaryTreeLevelKSize(root->_left, k - 1) +
        BinaryTreeLevelKSize(root->_right, k - 1);
}



// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    if (root == NULL) return NULL;
    if (root->_data == x) return root;
    BTNode* left = BinaryTreeFind(root->_left, x);
    if (left != NULL) return left;
    return BinaryTreeFind(root->_right, x);

}



// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
    if (root == NULL) return;
    printf("%c ", root->_data); // 先处理根节点 
    BinaryTreePrevOrder(root->_left);
    BinaryTreePrevOrder(root->_right);

}

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{

    if (root == NULL) return;
    BinaryTreeInOrder(root->_left);
    printf("%c ", root->_data); // 中处理根节点 
    BinaryTreeInOrder(root->_right);
}

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
    if (root == NULL) return;
    BinaryTreePostOrder(root->_left);
    BinaryTreePostOrder(root->_right);
    printf("%c ", root->_data); // 后处理根节点 

}

typedef struct {
    BTNode** data;
    int front, rear, size;
} Queue;

Queue* CreateQueue(int capacity) {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->data = (BTNode**)malloc(capacity * sizeof(BTNode*));
    q->front = q->rear = 0;
    q->size = 0;
    return q;
}

void EnQueue(Queue* q, BTNode* node) {
    q->data[q->rear++] = node;
    q->size++;
    if (q->rear == (sizeof(q->data) / sizeof(q->data[0]))) q->rear = 0;
}

BTNode* DeQueue(Queue* q) {
    BTNode* node = q->data[q->front];
    q->front = (q->front + 1) % (sizeof(q->data) / sizeof(q->data[0]));
    q->size--;
    return node;
}

void BinaryTreeLevelOrder(BTNode* root) {
    if (root == NULL) return;
    Queue* q = CreateQueue(100);
    EnQueue(q, root);
    while (q->size > 0) {
        BTNode* node = DeQueue(q);
        printf("%c ", node->_data);
        if (node->_left != NULL) EnQueue(q, node->_left);
        if (node->_right != NULL) EnQueue(q, node->_right);
    }
    free(q->data);
    free(q);
}

int BinaryTreeComplete(BTNode* root) {
    if (root == NULL) return 1;
    Queue* q = CreateQueue(100);
    EnQueue(q, root);
    int isLeaf = 0; // 标记是否遇到叶子节点 
    while (q->size > 0) {
        BTNode* node = DeQueue(q);
        if (node->_left) {
            if (isLeaf) return 0; // 已经遇到叶子后又出现子节点
            EnQueue(q, node->_left);
        }
        else {
            isLeaf = 1;
        }
        if (node->_right) {
            if (isLeaf) return 0;
            EnQueue(q, node->_right);
        }
        else {
            isLeaf = 1;
        }
        // 检查是否有右子树但无左子树 
        if (node->_right && !node->_left) return 0;
    }
    free(q->data);
    free(q);
    return 1;
}